import time

import numpy as np

# 创建一个空的二维列表，用于存储运行时间数据



def timer(data_list):
    # 定义一个装饰器，用于计算函数运行时间，并将结果存入二维列表中
    def decorator(func):
        # 定义一个内部函数，用于修饰原始函数
        def wrapper(*args, **kwargs):
            # 记录函数开始时间
            start = time.time()
            # 调用原始函数
            result = func(*args, **kwargs)
            # 记录函数结束时间
            end = time.time()
            # 将函数运行时间追加到对应的子列表中
            data_list[func.__name__].append(end - start)
            # 返回原始函数的返回值
            return result

        # 返回装饰后的函数
        return wrapper

    # 返回装饰器本身
    return decorator


# 直接插入
def insert(a):
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j] < a[j - 1]:
            a[j - 1], a[j] = a[j], a[j - 1]
            j -= 1
    return a


# 冒泡排序
def bubble(a):
    for i in range(0, len(a) - 1):
        for j in range(0, len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

# 快速排序
def quick(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    # left = [x for x in arr if x < pivot]
    # middle = [x for x in arr if x == pivot]
    # right = [x for x in arr if x > pivot]
    left = []
    middle = []
    right = []
    for x in arr:
        if x < pivot:
            left.append(x)
        elif x == pivot:
            middle.append(x)
        else:
            right.append(x)
    return quick(left) + middle + quick(right)


# 鸡尾酒算法
def cock_tail_sort(arr):
    for i in range(len(arr) // 2):
        # 有序标记，初始为True
        flag = True
        # 奇数轮，从左向右比较和交换
        for j in range(i, len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j + 1], arr[j] = arr[j], arr[j + 1]
                flag = False
        if flag:
            break
        # 偶数轮开始之前，要重新标记为True
        flag = True
        # 偶数轮，从右向左比较和交换
        for k in range(len(arr) - i - 1, i, -1):
            if arr[k] < arr[k - 1]:
                arr[k], arr[k - 1] = arr[k - 1], arr[k]
                flag = False
        if flag:
            break
    return arr


# 堆排序

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr


# 计数排序
def counting_sort(arr):
    # Convert the input to a numpy.ndarray
    arr = np.asarray(arr)

    # Find the unique elements of the array and their counts
    unique, counts = np.unique(arr, return_counts=True)

    # Repeat each unique element according to its count
    output = np.repeat(unique, counts)

    return output


# 希尔排序
# 定义一个希尔排序函数
def shell_sort(arr):
    # 获取数组的形状，即维度和每个维度的大小
    shape = arr.shape
    # 将数组展平为一维数组，方便进行排序
    arr = arr.flatten()
    # 获取一维数组的长度
    n = len(arr)
    # 设置初始的增量为数组长度的一半
    gap = n // 2
    # 当增量大于0时，进行希尔排序
    while gap > 0:
        # 对每个分组进行插入排序
        for i in range(gap, n):
            # 获取当前元素和它所在分组的第一个元素的索引
            temp = arr[i]
            j = i - gap
            # 在分组内，将当前元素与前面的元素比较，如果小于前面的元素，就交换位置，直到找到合适的位置或者到达分组的第一个元素为止
            while j >= 0 and temp < arr[j]:
                arr[j + gap] = arr[j]
                j -= gap
            # 将当前元素放到合适的位置上
            arr[j + gap] = temp
        # 减小增量，继续进行希尔排序
        gap //= 2

    # 将一维数组恢复为原来的形状，并返回结果
    return arr.reshape(shape)


# 归并排序
def merge_sort(alist):
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    # 采用归并排序后形成的有序的新列表
    left = merge_sort(alist[0:mid])
    right = merge_sort(alist[mid:])
    # 将两个有序的子序列合并为一个整体
    # merge(left, right)
    l_pointer, r_pointer = 0, 0
    result = []
    while l_pointer < len(left) and r_pointer < len(right):
        if left[l_pointer] <= right[r_pointer]:
            result.append(left[l_pointer])
            l_pointer += 1
        else:
            result.append(right[r_pointer])
            r_pointer += 1
    result.extend(left[l_pointer:])
    result.extend(right[r_pointer:])
    return np.array(result)
